home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1993 July / InfoMagic USENET CD-ROM July 1993.ISO / sources / misc / volume2 / pd-diff-v2 < prev    next >
Encoding:
Internet Message Format  |  1991-08-07  |  64.2 KB

  1. From: mark@jhereg.Jhereg.MN.ORG.UUCP (Mark H. Colburn)
  2. Newsgroups: comp.sources.misc
  3. Subject: v02i063: Yet another version of PD diff
  4. Message-ID: <7448@ncoast.UUCP>
  5. Date: 29 Feb 88 01:16:11 GMT
  6. Approved: allbery@ncoast.UUCP
  7.  
  8. Comp.sources.misc: Volume 2, Issue 63
  9. Submitted-By: "Mark H. Colburn" <mark@jhereg.Jhereg.MN.ORG>
  10. Archive-Name: pd-diff-v2
  11.  
  12. [Wonderful timing.  Anyone want to merge the new patches into the new diff?
  13. Sigh.  ++bsa]
  14.  
  15.     Here is yet another copy of the Public Domain Context Diff
  16. program which was first posted in January.  I have made some changes
  17. to speed it up quite significantly.  I have also merged all of the
  18. prior changes into the copy, updated the Makefile, README, etc.  Since the 
  19. diffs were quite large, I just thought that I would send you the whole
  20. thing.  Addition comments are at the tail of the README file.
  21.  
  22. --
  23. Mark H. Colburn            mark@jhereg.MN.ORG
  24.                         ihnp4!chinet!jhereg!mark
  25.  
  26. #! /bin/sh
  27. # This is a shell archive.  Remove anything before this line, then unpack
  28. # it by saving it into a file and typing "sh file".  To overwrite existing
  29. # files, type "sh file -c".  You can also feed this as standard input via
  30. # unshar, or by typing "sh <file", e.g..  If this archive is complete, you
  31. # will see the following message at the end:
  32. #        "End of shell archive."
  33. # Contents:  Makefile README TC-READ.ME diff.1 diff.c diff.doc diff.mem
  34. # Wrapped by mark@jhereg on Sat Feb 27 00:02:06 1988
  35. PATH=/bin:/usr/bin:/usr/ucb ; export PATH
  36. if test -f Makefile -a "${1}" != "-c" ; then 
  37.   echo shar: Will not over-write existing file \"Makefile\"
  38. else
  39. echo shar: Extracting \"Makefile\" \(1272 characters\)
  40. sed "s/^X//" >Makefile <<'END_OF_Makefile'
  41. X#
  42. X# Makefile for Public Domain Diff
  43. X#
  44. X# the two 'include' directive are for these USG 5.3 machines (or 3B1) which
  45. X# have shared libraries.  Comment them out if you do not have shared 
  46. X# libraries on your system.
  47. X
  48. Xinclude $(MAKEINC)/Makepre.h
  49. X
  50. X#
  51. X# You may want to use one or more of the following definitions when compiling,
  52. X# depending on what your target environment is, and whether you want debugging
  53. X# turned on or off.
  54. X#
  55. X#    TURBO   - compile for TURBO C target (See TC-READ.ME for details)
  56. X#    AMIGA   - compile for AMIGA target
  57. X#    OSK     - compile for OSK
  58. X#    DEBUG   - turn on debugging (implies TIMING) 
  59. X#    TIMING  - turn on timing code
  60. X#    MSC     - Microsoft C 4.0 (small model support)
  61. X#
  62. X# additional support for vax, or pdp11 are invoked by defining 'vax'
  63. X# or 'pdp11'.  These should be defined by your preprocessor if you are
  64. X# on one of these machines.
  65. X#
  66. X# CFLAGS = -O -DTURBOC
  67. XCFLAGS = -O
  68. XLDFLAGS = -s
  69. X
  70. X# The first line ('cc ...') is for standard C compilers, the second line
  71. X# ('$(LD) ...') is for shared library machines.  Use whichever line is 
  72. X# appropriate for your system and comment the other one out.
  73. X
  74. Xdiff: diff.o
  75. X#    cc $(LDFLAGS) diff.o -o diff
  76. X    $(LD) $(SHAREDLIB) $(LDFLAGS) diff.o -o diff
  77. X
  78. Xclean:
  79. X    rm -f *.o a.out core diff
  80. X
  81. Xinclude $(MAKEINC)/Makepost.h
  82. END_OF_Makefile
  83. if test 1272 -ne `wc -c <Makefile`; then
  84.     echo shar: \"Makefile\" unpacked with wrong size!
  85. fi
  86. # end of overwriting check
  87. fi
  88. if test -f README -a "${1}" != "-c" ; then 
  89.   echo shar: Will not over-write existing file \"README\"
  90. else
  91. echo shar: Extracting \"README\" \(4508 characters\)
  92. sed "s/^X//" >README <<'END_OF_README'
  93. XComp.sources.misc: Volume 2, Issue 1
  94. XArchive-Name: pd-diff
  95. XSubmitted-By: blarson@skat.usc.edu (Bob Larson)
  96. X
  97. XHere's a public domain diff with the -b and -c options.  (4.2bsd style
  98. Xcontex diffs.)  I wasn't aware that these wern't present in all unix
  99. Xversions of diff, so I didn't think posting it was a priority.  It's
  100. Xlarge, slow, and many of the comments are no longer true, but it does
  101. Xwork.  (except when it runs out of memory)  The one case I know of
  102. Xwhere its output is incompatable with patch does seem to be pretty
  103. Xrare.  No makefile is included, the 4.2bsd diff is better on the unix
  104. Xsystem I use.  If you don't know how to compile and load a single C
  105. Xprogram, this probably isn't the tool for you anyway.  I'd be grateful
  106. Xto anyone who cleans this up and documents it properly.  It does
  107. Xappear to have been separate files at some point, I'm presenting it in
  108. Xa form similar to how I got it: mail headers and outdated documentation
  109. Xin comments and all.  I just banged on it enough to get it doing what
  110. XI wanted.
  111. X
  112. X---
  113. XComp.Sources.Misc: Volume 2, Issue 8
  114. XSubmitted-By: <mike2@lcuxa.UUCP>
  115. XArchive-Name: cdiff-v2
  116. X
  117. XAfter receiving Bob Larson's sources for the PD context diff program,
  118. XI decided to accept his challenge to rewrite the documentation.  In
  119. Xthe process, I also ported it to TURBOC version 1.5.  It probably will
  120. Xalso compile in TURBOC 1.0, but since getting the update I dispensed
  121. Xwith the previous version and did not try it.  
  122. X
  123. XThe code has been reorganized to strip it of the documentation that
  124. Xwas built into it; that has been moved to the file cdiff.mem.  Thus,
  125. Xthe following shar file includes cdiff.c, cdiff.1 (man source), cdiff.mem
  126. X(the previously built-in documentation), cdiff.doc (cdiff.1 passed
  127. Xthrough nroff -man for those who do not have nroff available), the
  128. Xoriginal README, and a new TC-READ.ME.  Follow the notes in TC-READ.ME
  129. Xor it will run even slower!  
  130. X
  131. XOf course, no warranties whatsoever go with this.  I merely hacked the
  132. Xcode minimally.  I didn't write it.
  133. X---
  134. X
  135. XComp.sources.misc: Volume 2, Issue 59
  136. XSubmitted-By: <mike2@lcuxa.UUCP>
  137. XArchive-Name: pd-cdiff-patch
  138. X
  139. XNeil Dixon uncovered a flaw in the logic of the cdiff program that
  140. Xwas distributed early in January, and which was redistributed with
  141. Xchanges to make it compilable in Turbo C.  I've tested his patch
  142. Xboth on the Unix SysVr2 version and on the PC, and have not found
  143. Xany errors.  Conversely, the earlier version when compiled in MSC
  144. X4.0 (but, for some reason, not when compiled in TC 1.5) would
  145. Xsporadically come up with "read" errors.  Since it now works in MSC as
  146. Xwell as TC, I've included the appropriate ifdefs for both compilers,
  147. Xand have incorporated Neil's patch.  (This was for clarity.  The line
  148. Xnumbers in his patch did not correspond precisely to the line numbers
  149. Xin the distributed code.)  Both the patch as sent to me and the
  150. Xrevised code are contained below.
  151. X
  152. XAs before, I did not write this code.  I merely ported it, and of
  153. Xcourse make no warranties whatsoever.
  154. X
  155. X---
  156. X
  157. XOk, I guess that I will add my two cents worth.  Here is yet another
  158. Xrepost of the public domain diff program.  
  159. X
  160. XI have integrated some changes into the i/o portion of the code, providing 
  161. Xsome significant speedups.  These changes were made after spending two 
  162. Xevenings playging around with the profiler, attempting various fixes to
  163. Xmake this beast a little faster.  I completed this prior to the latest release 
  164. Xof the code (the version listed immediately above).  
  165. X
  166. XI have attempted to merge the changes provided by Mike above, but, since I do 
  167. Xnot have any other machines close by, I could not test them.
  168. X
  169. XThe changes which I made are in the following areas:
  170. X
  171. X    * modified the fgetss() and fputss() routines.  These were the primary
  172. X      areas of intense activity on the system.  From the source that I
  173. X      could see, these changes should be portable.  After timing this 
  174. X      on my 3b1, the changes make this diff run at about the same speed
  175. X      as the system diff for the files that I was using (amazing isn't it?).
  176. X
  177. X    * Moved the defines from within the source code to within the Makefile.
  178. X
  179. X    * Ran the code through indent.  Sorry about that, but it was the only
  180. X      way that I could make sure that I got all the other patches integrated 
  181. X      properly.
  182. X
  183. X    * Cleaned up some of the comments and added a few of my own.
  184. X
  185. X    * Made a few tweaks to make lint happier.
  186. X
  187. X    * Modified the Makefile to allow use of shared libraries.  Included
  188. X     instructions for all the defines in the system as well.
  189. X
  190. XMark H. Colburn (mark@jhereg.mn.org)
  191. END_OF_README
  192. if test 4508 -ne `wc -c <README`; then
  193.     echo shar: \"README\" unpacked with wrong size!
  194. fi
  195. # end of overwriting check
  196. fi
  197. if test -f TC-READ.ME -a "${1}" != "-c" ; then 
  198.   echo shar: Will not over-write existing file \"TC-READ.ME\"
  199. else
  200. echo shar: Extracting \"TC-READ.ME\" \(419 characters\)
  201. sed "s/^X//" >TC-READ.ME <<'END_OF_TC-READ.ME'
  202. X
  203. X1.  Make certain that the first line is a #define TURBO 1 line.
  204. X2.  Compile in the Large model.
  205. X3.  Set the optimizations:
  206. X    a) to optimize for speed, not size
  207. X    b) to use register variables
  208. X    c) to invoke register optimization
  209. X    c) to invoke jump optimization
  210. X4.  Even with the foregoing, this program can run slowly on a large file
  211. X    (as much as 60 seconds to compare two 40K files in a 4.77 MHz PC!)
  212. X    Be patient.
  213. X
  214. END_OF_TC-READ.ME
  215. if test 419 -ne `wc -c <TC-READ.ME`; then
  216.     echo shar: \"TC-READ.ME\" unpacked with wrong size!
  217. fi
  218. # end of overwriting check
  219. fi
  220. if test -f diff.1 -a "${1}" != "-c" ; then 
  221.   echo shar: Will not over-write existing file \"diff.1\"
  222. else
  223. echo shar: Extracting \"diff.1\" \(4000 characters\)
  224. sed "s/^X//" >diff.1 <<'END_OF_diff.1'
  225. X.TH DIFF 1
  226. X.SH NAME
  227. Xdiff \- Public Domain diff (context diff) program
  228. X.SH SYNOPSIS
  229. X.B diff
  230. X[
  231. X.B \-b \-c \-i \-e
  232. X] file1 file2
  233. X.SH DESCRIPTION
  234. X.I Diff\^
  235. Xcompares two files, showing what must be changed to make them
  236. Xidentical. Either file1 or file2 (but not both) may refer to
  237. Xdirectories. If that is the case, a file in the directory whose
  238. Xname is the same as the other file argument will be used. The
  239. Xstandard input may be used for one of the files by replacing the
  240. Xargument by "-". Except for the standard input, both files must
  241. Xbe on disk devices.
  242. X.SH OPTIONS
  243. X.HP
  244. X.B \-b  
  245. XRemove trailing whitespace (blanks and tabs)
  246. Xand compress all other strings of whitespace to a single blank.
  247. X.HP
  248. X.B \-c  
  249. XPrint some context -- matching lines before
  250. Xand after the non-match section.  Mark non-matched sections
  251. Xwith "|".
  252. X.HP
  253. X.B \-i  
  254. XIgnore lower/upper case distinctions.
  255. X.HP
  256. X.B \-e  
  257. XOutput is in an "editor script" format which
  258. Xis compatible with the Unix 'ed' editor.
  259. X.PP
  260. XAll information needed to compare the files is maintained in main
  261. Xmemory. This means that very large files (or fairly large files
  262. Xwith many differences) will cause the program to abort with an
  263. X"out of space" message. Main memory requirements (in words) are
  264. Xapproximately:
  265. X.br
  266. X
  267. X.ce
  268. X2 * (length of file1 + length of file2)
  269. X.br
  270. X.ce
  271. X+ 3 * (number of changes)
  272. X.br
  273. X.PP
  274. X(Where "length" is the number of lines of data in each file.)
  275. X.PP
  276. XThe algorithm reads each file twice, once to build hash tables
  277. Xand once to check for fortuitous matches (two lines that are in
  278. Xfact different, but which have the same hash value). CPU time
  279. Xrequirements include sorting the hash tables and randomly
  280. Xsearching memory tables for equivalence classes. For example, on
  281. Xa time-shared VAX-11/780, comparing two 1000 line files required
  282. Xabout 30 seconds (elapsed clock time) and about 10,000 bytes of
  283. Xworking storage. About 90 per-cent of the time was taken up by
  284. Xfile I/O.
  285. X.SH DIAGNOSTICS
  286. X.HP
  287. XWarning, bad option 'x'
  288. X.br
  289. XThe option is ignored.
  290. X.HP
  291. XUsage ...
  292. X.br
  293. XTwo input files were not specified.
  294. X.HP
  295. XCan't open input file "filename".
  296. X.br
  297. XCan't continue.
  298. X.HP
  299. XOut of space
  300. X.br
  301. XThe program ran out of memory while comparing the two files.
  302. X.HP
  303. XCan't read line nnn at xxx in file[A/B]
  304. X.br
  305. XThis indicates an I/O error when seeking to the specific line.
  306. XIt should not happen.
  307. X.HP
  308. XSpurious match, output is not optimal.
  309. X.br
  310. XTwo lines that were different yielded the same hash value.  This is
  311. Xharmless except that the difference output is not the minimum set of
  312. Xdifferences between the two files.  For example, instead of the output:
  313. X.ce
  314. Xlines 1 to 5 were changed to ...
  315. X.br
  316. Xthe program will print
  317. X.ce
  318. Xlines 1 to 3 were changed to ...
  319. X.br
  320. X.ce
  321. Xlines 4 to 5 were changed to ...
  322. X.br
  323. X.HP
  324. XThe program uses a CRC16 hash code.
  325. X.br
  326. XThe likelihood of this error is
  327. Xquite small.
  328. X.SH AUTHOR
  329. XThe diff algorithm was developed by J. W. Hunt and M. D. McIlroy,
  330. Xusing a central algorithm defined by H. S. Stone.
  331. XIt was published in:
  332. X.in +5
  333. X.nf
  334. XHunt, J. W., and McIlroy, M. D.,
  335. XAn Algorithm for Differential File Comparison,
  336. XComputing Science Technical Report #41,
  337. XBell Laboratories, Murray Hill, NJ  07974
  338. X.fi
  339. X.in -5
  340. X.SH BUGS
  341. XOn RSX and DECUS C on VMS systems, diff may fail if the both
  342. Xfiles are not "variable-length, implied carriage control" format.
  343. XThe scopy program can be used to convert files to this format if
  344. Xproblems arise.
  345. X.PP
  346. XWhen compiled under VAX C, diff handles STREAM_LF files properly
  347. X(in addition to the canonical variable-length implied carriage
  348. Xcontrol files). Other variations should work, but have not been
  349. Xtested.
  350. X.PP
  351. XWhen compiled under VAX C, diff is quite slow for unknown reasons
  352. Xwhich ought to be investigated. On the other hand, it has access
  353. Xto effectively unlimited memory.
  354. X.PP
  355. XOutput in a form suitable for ed - the -e option - seems rather
  356. Xpointless; the analogue on DEC systems is SLP (SUMSLP on VMS). It
  357. Xwould be simple to provide SLP-compatible output. The question
  358. Xis, why bother - since the various DEC file comparison utilities
  359. Xalready produce it.
  360. END_OF_diff.1
  361. if test 4000 -ne `wc -c <diff.1`; then
  362.     echo shar: \"diff.1\" unpacked with wrong size!
  363. fi
  364. # end of overwriting check
  365. fi
  366. if test -f diff.c -a "${1}" != "-c" ; then 
  367.   echo shar: Will not over-write existing file \"diff.c\"
  368. else
  369. echo shar: Extracting \"diff.c\" \(33595 characters\)
  370. sed "s/^X//" >diff.c <<'END_OF_diff.c'
  371. X/*
  372. X * diff.c - public domain context diff program
  373. X *
  374. X */
  375. X
  376. X#ifdef TURBO
  377. X#include <alloc.h>
  378. X#include <errno.h>
  379. X#include <process.h>
  380. X#include <stdio.h>
  381. X#include <stdlib.h>
  382. X#include <string.h>
  383. X
  384. X#else /* !TURBO */
  385. X#include <stdio.h>
  386. X#include <ctype.h>
  387. X#endif /* TURBO */
  388. X
  389. X#ifdef vms
  390. X#include      <ssdef.h>
  391. X#include      <stsdef.h>
  392. X#define  IO_SUCCESS  (SS | STS)
  393. X#define  IO_ERROR  SS
  394. X#endif /* vms */
  395. X
  396. X/*
  397. X * Note: IO_SUCCESS and IO_ERROR are defined in the Decus C stdio.h file
  398. X */
  399. X
  400. X#ifndef  IO_SUCCESS
  401. X#define  IO_SUCCESS  0
  402. X#endif /* IO_SUCCESS */
  403. X#ifndef  IO_ERROR
  404. X#define  IO_ERROR  1
  405. X#endif /* IO_ERROR */
  406. X
  407. X#define  EOS      0
  408. X#ifdef unix
  409. Xchar            temfile[L_tmpnam];
  410. Xchar           *tmpnam();
  411. X#define  TEMPFILE  (temfile[0]? temfile: (tmpnam(temfile), temfile))
  412. X#else /* unix */
  413. X#define  TEMPFILE  "diff.tmp"
  414. X#endif /* unix */
  415. X#define  TRUE      1
  416. X#define  FALSE      0
  417. X
  418. X#ifdef  pdp11
  419. X#define  short  int
  420. X#endif /* pdp11 */
  421. X
  422. Xtypedef struct candidate {
  423. X    int             b;            /* Line in fileB       */
  424. X    int             a;            /* Line in fileA       */
  425. X    int             link;        /* Previous candidate       */
  426. X} CANDIDATE;
  427. X
  428. Xtypedef struct line {
  429. X    unsigned short  hash;        /* Hash value etc.       */
  430. X    short           serial;        /* Line number        */
  431. X} LINE;
  432. X
  433. XLINE           *file[2];        /* Hash/line for total file  */
  434. X#define  fileA  file[0]
  435. X#define  fileB  file[1]
  436. X
  437. XLINE           *sfile[2];        /* Hash/line after prefix  */
  438. X#define  sfileA  sfile[0]
  439. X#define  sfileB  sfile[1]
  440. X
  441. Xint             len[2];            /* Actual lines in each file  */
  442. X#define  lenA  len[0]
  443. X#define  lenB  len[1]
  444. X
  445. Xint             slen[2];        /* Squished lengths       */
  446. X#define  slenA  slen[0]
  447. X#define  slenB  slen[1]
  448. X
  449. Xint             prefix;            /* Identical lines at start  */
  450. Xint             suffix;            /* Identical lenes at end  */
  451. X
  452. XFILE           *infd[2] = {NULL, NULL};    /* Input file identifiers  */
  453. XFILE           *tempfd;            /* Temp for input redirection  */
  454. X
  455. Xextern long     ftell();
  456. Xextern FILE    *fopen();
  457. X
  458. X#ifdef TURBO
  459. Xextern void    *malloc();
  460. X#else /* !TURBO */
  461. Xextern char    *malloc();
  462. X#endif /* TURBO */
  463. X
  464. Xchar           *fgetss();
  465. Xunsigned short  hash();
  466. X
  467. X#ifdef    AMIGA
  468. X/* Define these types for Amiga C */
  469. Xchar           *savptr;
  470. Xint             savsiz;
  471. Xchar           *wrk;
  472. Xchar           *wrk2;
  473. Xint             cpysiz;
  474. X#endif /* AMIGA */
  475. X
  476. X/*
  477. X * The following vectors overlay the area defined by fileA
  478. X */
  479. X
  480. Xshort          *class;            /* Unsorted line numbers  */
  481. Xint            *klist;            /* Index of element in clist  */
  482. XCANDIDATE      *clist;            /* Storage pool for candidates  */
  483. Xint             clength = 0;    /* Number of active candidates  */
  484. X#define    CSIZE_INC 50            /* How many to allocate each time we have to */
  485. Xint             csize = CSIZE_INC;        /* Current size of storage pool */
  486. X
  487. Xint            *match;            /* Longest subsequence       */
  488. Xlong           *oldseek;        /* Seek position in file A  */
  489. X
  490. X/*
  491. X * The following vectors overlay the area defined by fileB
  492. X */
  493. X
  494. Xshort          *member;            /* Concatenated equiv. classes  */
  495. Xlong           *newseek;        /* Seek position in file B  */
  496. Xchar           *textb;            /* Input from file2 for check  */
  497. X
  498. X/*
  499. X * Global variables
  500. X */
  501. X
  502. Xint             eflag = FALSE;    /* Edit script requested  */
  503. Xint             bflag = FALSE;    /* Blank supress requested  */
  504. Xint             cflag = FALSE;    /* Context printout       */
  505. Xint             iflag = FALSE;    /* Ignore case requested  */
  506. Xchar            text[257];        /* Input line from file1  */
  507. Xextern char    *myalloc();        /* Storage allocator       */
  508. X
  509. Xextern char    *compact();        /* Storage compactor       */
  510. X
  511. X#ifdef  DEBUG
  512. X#ifndef OSK
  513. X#define  TIMING
  514. X#endif /* OSK */
  515. X#endif /* DEBUG */
  516. X#ifdef  TIMING
  517. Xextern long     time();
  518. Xextern char    *4532mend;
  519. Xlong            totaltime;
  520. Xlong            sectiontime;
  521. Xchar           *mstart;
  522. X#endif /* TIMING */
  523. Xvoid            free();
  524. Xvoid            exit();
  525. X#ifndef OSK
  526. Xvoid            perror();
  527. X#endif /* OSK */
  528. X
  529. X/*
  530. X * Diff main program
  531. X */
  532. X
  533. Xmain(argc, argv)
  534. X    int             argc;
  535. X    char          **argv;
  536. X{
  537. X    register int    i;
  538. X    register char  *ap;
  539. X
  540. X#ifdef OSK
  541. X    extern int      _memmins;
  542. X    _memmins = 16 * 1024;        /* tell OSK we will malloc a lot */
  543. X#endif /* OSK */
  544. X#ifdef  TIMING
  545. X    sectiontime = time(&totaltime);
  546. X#endif /* TIMING */
  547. X#ifdef vms
  548. X    argc = getredirection(argc, argv);
  549. X#endif /* vms */
  550. X    while (argc > 1 && *(ap = argv[1]) == '-' && *++ap != EOS) {
  551. X        while (*ap != EOS) {
  552. X            switch ((*ap++)) {
  553. X            case 'b':
  554. X                bflag++;
  555. X                break;
  556. X
  557. X            case 'c':
  558. X                if (*ap > '0' && *ap <= '9')
  559. X                    cflag = *ap++ - '0';
  560. X                else
  561. X                    cflag = 3;
  562. X                break;
  563. X
  564. X            case 'e':
  565. X                eflag++;
  566. X                break;
  567. X
  568. X            case 'i':
  569. X                iflag++;
  570. X                break;
  571. X
  572. X            default:
  573. X                fprintf(stderr,
  574. X                        "Warning, bad option '%c'\n",
  575. X                        ap[-1]);
  576. X                break;
  577. X            }
  578. X        }
  579. X        argc--;
  580. X        argv++;
  581. X    }
  582. X
  583. X    if (argc != 3)
  584. X        error("Usage: diff [-options] file1 file2");
  585. X    if (cflag && eflag) {
  586. X        fprintf(stderr,
  587. X                "Warning, -c and -e are incompatible, -c supressed.\n");
  588. X        cflag = FALSE;
  589. X    }
  590. X    argv++;
  591. X    for (i = 0; i <= 1; i++) {
  592. X        if (argv[i][0] == '-' && argv[i][1] == EOS) {
  593. X            infd[i] = stdin;
  594. X            if ((tempfd = fopen(TEMPFILE, "w")) == NULL)
  595. X                cant(TEMPFILE, "work", 1);
  596. X        } else {
  597. X            infd[i] = fopen(argv[i], "r");
  598. X            if (!infd[i])
  599. X                cant(argv[i], "input", 2);        /* Fatal error */
  600. X        }
  601. X    }
  602. X
  603. X    if (infd[0] == stdin && infd[1] == stdin)
  604. X        error("Can't diff two things both on standard input.");
  605. X
  606. X    if (infd[0] == NULL && infd[1] == NULL) {
  607. X        cant(argv[0], "input", 0);
  608. X        cant(argv[1], "input", 1);
  609. X    }
  610. X#ifdef vms
  611. X    else if (infd[1] == NULL)
  612. X        opendir(1, &argv[1], infd[0]);
  613. X    else if (infd[0] == NULL)
  614. X        opendir(0, &argv[0], infd[1]);
  615. X#endif /* vms */
  616. X
  617. X    /*
  618. X     * Read input, building hash tables. 
  619. X     */
  620. X    input(0);
  621. X    input(1);
  622. X    squish();
  623. X#ifdef  DEBUG
  624. X    printf("before sort\n");
  625. X    for (i = 1; i <= slenA; i++)
  626. X        printf("sfileA[%d] = %6d %06o\n",
  627. X               i, sfileA[i].serial, sfileA[i].hash);
  628. X    for (i = 1; i <= slenB; i++)
  629. X        printf("sfileB[%d] = %6d %06o\n",
  630. X               i, sfileB[i].serial, sfileB[i].hash);
  631. X#endif /* DEBUG */
  632. X    sort(sfileA, slenA);
  633. X    sort(sfileB, slenB);
  634. X#ifdef  TIMING
  635. X    ptime("input");
  636. X#endif /* TIMING */
  637. X#ifdef  DEBUG
  638. X    printf("after sort\n");
  639. X    for (i = 1; i <= slenA; i++)
  640. X        printf("sfileA[%d] = %6d %06o\n",
  641. X               i, sfileA[i].serial, sfileB[i].hash);
  642. X    for (i = 1; i <= slenB; i++)
  643. X        printf("sfileB[%d] = %6d %06o\n",
  644. X               i, sfileB[i].serial, sfileB[i].hash);
  645. X#endif /* DEBUG */
  646. X
  647. X    /*
  648. X     * Build equivalence classes. 
  649. X     */
  650. X    member = (short *) fileB;
  651. X    equiv();
  652. X    member = (short *) compact((char *) member, (slenB + 2) * sizeof(int),
  653. X                               "squeezing member vector");
  654. X
  655. X    /*
  656. X     * Reorder equivalence classes into array class[] 
  657. X     */
  658. X    class = (short *) fileA;
  659. X    unsort();
  660. X    class = (short *) compact((char *) class, (slenA + 2) * sizeof(int),
  661. X                              "compacting class vector");
  662. X#ifdef  TIMING
  663. X    ptime("equiv/unsort");
  664. X#endif /* TIMING */
  665. X
  666. X    /*
  667. X     * Find longest subsequences 
  668. X     */
  669. X    klist = (int *) myalloc((slenA + 2) * sizeof(int), "klist");
  670. X    clist = (CANDIDATE *) myalloc(csize * sizeof(CANDIDATE), "clist");
  671. X    i = subseq();
  672. X#ifndef OSK
  673. X    free((char *) member);
  674. X    free((char *) class);
  675. X#else /* OSK */
  676. X    free((char *) member - sizeof(int));
  677. X    free((char *) class - sizeof(int));
  678. X#endif /* OSK */
  679. X    match = (int *) myalloc((lenA + 2) * sizeof(int), "match");
  680. X    unravel(klist[i]);
  681. X#ifndef OSK
  682. X    free((char *) clist);
  683. X    free((char *) klist);
  684. X#else /* OSK */
  685. X    free((char *) clist - sizeof(int));
  686. X    free((char *) klist - sizeof(int));
  687. X#endif /* OSK */
  688. X#ifdef  TIMING
  689. X    ptime("subsequence/unravel");
  690. X#endif /* TIMING */
  691. X
  692. X    /*
  693. X     * Check for fortuitous matches and output differences 
  694. X     */
  695. X    oldseek = (long *) myalloc((lenA + 2) * sizeof(*oldseek), "oldseek");
  696. X    newseek = (long *) myalloc((lenB + 2) * sizeof(*newseek), "newseek");
  697. X    textb = myalloc(sizeof text, "textbuffer");
  698. X    if (check(argv[0], argv[1]))
  699. X        fprintf(stderr, "Spurious match, output is not optimal\n");
  700. X#ifdef  TIMING
  701. X    ptime("check");
  702. X#endif /* TIMING */
  703. X    output(argv[0], argv[1]);
  704. X#ifdef  TIMING
  705. X    ptime("output");
  706. X    printf("%ld seconds required\n", sectiontime - totaltime);
  707. X#endif /* TIMING */
  708. X    if (tempfd != NULL) {
  709. X        fclose(tempfd);
  710. X#ifdef unix
  711. X        unlink(TEMPFILE);
  712. X#else /* !unix */
  713. X#ifdef OSK
  714. X        unlink(TEMPFILE);
  715. X#else /* OSK */
  716. X#ifdef MSC                        /* MSC 4.0 does not understand disjunctive
  717. X                                 * #if's.  */
  718. X        unlink(TEMPFILE);
  719. X#else /* MSC */
  720. X        remove(TEMPFILE);
  721. X#endif /* MSC */
  722. X#endif /* OSK */
  723. X#endif /* unxi */
  724. X    }
  725. X    return(0);
  726. X}
  727. X
  728. X
  729. X/*
  730. X * Read the file, building hash table
  731. X */
  732. X
  733. Xinput(which)
  734. X    int             which;        /* 0 or 1 to redefine infd[]  */
  735. X{
  736. X    register LINE  *lentry;
  737. X    register int    linect = 0;
  738. X    FILE           *fd;
  739. X#define    LSIZE_INC 200            /* # of line entries to alloc at once */
  740. X    int             lsize = LSIZE_INC;
  741. X
  742. X    lentry = (LINE *) myalloc(sizeof(LINE) * (lsize + 3), "line");
  743. X    fd = infd[which];
  744. X    while (!getline(fd, text)) {
  745. X        if (++linect >= lsize) {
  746. X            lsize += 200;
  747. X            lentry = (LINE *) compact((char *) lentry,
  748. X                                      (lsize + 3) * sizeof(LINE),
  749. X                                      "extending line vector");
  750. X        }
  751. X        lentry[linect].hash = hash(text);
  752. X    }
  753. X
  754. X    /*
  755. X     * If input was from stdin ("-" command), finish off the temp file. 
  756. X     */
  757. X    if (fd == stdin) {
  758. X        fclose(tempfd);
  759. X        tempfd = infd[which] = fopen(TEMPFILE, "r");
  760. X    }
  761. X
  762. X    /*
  763. X     * If we wanted to be stingy with memory, we could realloc lentry down to
  764. X     * its exact size (+3 for some odd reason) here.  No need?  
  765. X     */
  766. X    len[which] = linect;
  767. X    file[which] = lentry;
  768. X}
  769. X
  770. X
  771. X/*
  772. X * Look for initial and trailing sequences that have identical hash values.
  773. X * Don't bother building them into the candidate vector.
  774. X */
  775. X
  776. Xsquish()
  777. X{
  778. X    register int    i;
  779. X    register LINE  *ap;
  780. X    register LINE  *bp;
  781. X    int             j;
  782. X    int             k;
  783. X
  784. X    /*
  785. X     * prefix -> first line (from start) that doesn't hash identically 
  786. X     */
  787. X    i = 0;
  788. X    ap = &fileA[1];
  789. X    bp = &fileB[1];
  790. X    while (i < lenA && i < lenB && ap->hash == bp->hash) {
  791. X        i++;
  792. X        ap++;
  793. X        bp++;
  794. X    }
  795. X    prefix = i;
  796. X
  797. X    /*
  798. X     * suffix -> first line (from end) that doesn't hash identically 
  799. X     */
  800. X    j = lenA - i;
  801. X    k = lenB - i;
  802. X    ap = &fileA[lenA];
  803. X    bp = &fileB[lenB];
  804. X    i = 0;
  805. X    while (i < j && i < k && ap->hash == bp->hash) {
  806. X        i++;
  807. X        ap--;
  808. X        bp--;
  809. X    }
  810. X    suffix = i;
  811. X
  812. X    /*
  813. X     * Tuck the counts away 
  814. X     */
  815. X    for (k = 0; k <= 1; k++) {
  816. X        sfile[k] = file[k] + prefix;
  817. X        j = slen[k] = len[k] - prefix - suffix;
  818. X
  819. X        for (i = 0, ap = sfile[k]; i <= slen[k]; i++, ap++) {
  820. X            ap->serial = i;
  821. X        }
  822. X    }
  823. X}
  824. X
  825. X
  826. X/*
  827. X * Sort hash entries
  828. X */
  829. X
  830. Xsort(vector, vecsize)
  831. X    LINE           *vector;        /* What to sort        */
  832. X    int             vecsize;    /* How many to sort       */
  833. X{
  834. X    register int    j;
  835. X    register LINE  *aim;
  836. X    register LINE  *ai;
  837. X    int             mid;
  838. X    int             k;
  839. X    LINE            work;
  840. X
  841. X    for (j = 1; j <= vecsize; j *= 2);
  842. X    mid = (j - 1);
  843. X    while ((mid /= 2) != 0) {
  844. X        k = vecsize - mid;
  845. X        for (j = 1; j <= k; j++) {
  846. X            for (ai = &vector[j]; ai > vector; ai -= mid) {
  847. X                aim = &ai[mid];
  848. X                if (aim < ai)
  849. X                    break;        /* ?? Why ??       */
  850. X                if (aim->hash > ai->hash ||
  851. X                    aim->hash == ai->hash &&
  852. X                    aim->serial > ai->serial)
  853. X                    break;
  854. X                work.hash = ai->hash;
  855. X                ai->hash = aim->hash;
  856. X                aim->hash = work.hash;
  857. X                work.serial = ai->serial;
  858. X                ai->serial = aim->serial;
  859. X                aim->serial = work.serial;
  860. X            }
  861. X        }
  862. X    }
  863. X}
  864. X
  865. X
  866. X/*
  867. X * Build equivalence class vector
  868. X */
  869. X
  870. Xequiv()
  871. X{
  872. X    register LINE  *ap;
  873. X    union {
  874. X        LINE           *bp;
  875. X        short          *mp;
  876. X    }               r;
  877. X    register int    j;
  878. X    LINE           *atop;
  879. X
  880. X#ifdef  DEBUG
  881. X    printf("equiv entry\n");
  882. X    for (j = 1; j <= slenA; j++)
  883. X        printf("sfileA[%d] = %6d %06o\n",
  884. X               j, sfileA[j].serial, sfileA[j].hash);
  885. X    for (j = 1; j <= slenB; j++)
  886. X        printf("sfileB[%d] = %6d %06o\n",
  887. X               j, sfileB[j].serial, sfileB[j].hash);
  888. X#endif /* DEBUG */
  889. X    j = 1;
  890. X    ap = &sfileA[1];
  891. X    r.bp = &sfileB[1];
  892. X    atop = &sfileA[slenA];
  893. X    while (ap <= atop && j <= slenB) {
  894. X        if (ap->hash < r.bp->hash) {
  895. X            ap->hash = 0;
  896. X            ap++;
  897. X        } else if (ap->hash == r.bp->hash) {
  898. X            ap->hash = j;
  899. X            ap++;
  900. X        } else {
  901. X            r.bp++;
  902. X            j++;
  903. X        }
  904. X    }
  905. X    while (ap <= atop) {
  906. X        ap->hash = 0;
  907. X        ap++;
  908. X    }
  909. X    sfileB[slenB + 1].hash = 0;
  910. X#ifdef  DEBUG
  911. X    printf("equiv exit\n");
  912. X    for (j = 1; j <= slenA; j++)
  913. X        printf("sfileA[%d] = %6d %06o\n",
  914. X               j, sfileA[j].serial, sfileA[j].hash);
  915. X    for (j = 1; j <= slenB; j++)
  916. X        printf("sfileB[%d] = %6d %06o\n",
  917. X               j, sfileB[j].serial, sfileB[j].hash);
  918. X#endif /* DEBUG */
  919. X    ap = &sfileB[0];
  920. X    atop = &sfileB[slenB];
  921. X    r.mp = &member[0];
  922. X    while (++ap <= atop) {
  923. X        r.mp++;
  924. X        *r.mp = -(ap->serial);
  925. X        while (ap[1].hash == ap->hash) {
  926. X            ap++;
  927. X            r.mp++;
  928. X            *r.mp = ap->serial;
  929. X        }
  930. X    }
  931. X    r.mp[1] = -1;
  932. X#ifdef  DEBUG
  933. X    for (j = 0; j <= slenB; j++)
  934. X        printf("member[%d] = %d\n", j, member[j]);
  935. X#endif /* DEBUG */
  936. X}
  937. X
  938. X
  939. X/*
  940. X * Build class vector
  941. X */
  942. X
  943. Xunsort()
  944. X{
  945. X    register int   *temp;
  946. X    register int   *tp;
  947. X    union {
  948. X        LINE           *ap;
  949. X        short          *cp;
  950. X    }               u;
  951. X    LINE           *evec;
  952. X    short          *eclass;
  953. X#ifdef  DEBUG
  954. X    int             i;
  955. X#endif /* DEBUG */
  956. X
  957. X    temp = (int *) myalloc((slenA + 1) * sizeof(int), "unsort scratch");
  958. X    u.ap = &sfileA[1];
  959. X    evec = &sfileA[slenA];
  960. X    while (u.ap <= evec) {
  961. X#ifdef  DEBUG
  962. X        printf("temp[%2d] := %06o\n", u.ap->serial, u.ap->hash);
  963. X#endif /* DEBUG */
  964. X        temp[u.ap->serial] = u.ap->hash;
  965. X        u.ap++;
  966. X    }
  967. X
  968. X    /*
  969. X     * Copy into class vector and free work space 
  970. X     */
  971. X    u.cp = &class[1];
  972. X    eclass = &class[slenA];
  973. X    tp = &temp[1];
  974. X    while (u.cp <= eclass)
  975. X        *u.cp++ = *tp++;
  976. X#ifndef OSK
  977. X    free((char *) temp);
  978. X#else /* OSK */
  979. X    free((char *) temp - sizeof(int));
  980. X#endif /* OSK */
  981. X#ifdef  DEBUG
  982. X    printf("unsort exit\n");
  983. X    for (i = 1; i <= slenA; i++)
  984. X        printf("class[%d] = %d %06o\n", i, class[i], class[i]);
  985. X#endif /* DEBUG */
  986. X}
  987. X
  988. X
  989. X/*
  990. X * Generate maximum common subsequence chain in clist[]
  991. X */
  992. X
  993. Xsubseq()
  994. X{
  995. X    int             a;
  996. X    register unsigned ktop;
  997. X    register int    b;
  998. X    register int    s;
  999. X    unsigned        r;
  1000. X    int             i;
  1001. X    int             cand;
  1002. X
  1003. X    klist[0] = newcand(0, 0, -1);
  1004. X    klist[1] = newcand(slenA + 1, slenB + 1, -1);
  1005. X    ktop = 1;                    /* -> guard entry  */
  1006. X    for (a = 1; a <= slenA; a++) {
  1007. X
  1008. X        /*
  1009. X         * For each non-zero element in fileA ... 
  1010. X         */
  1011. X        if ((i = class[a]) == 0)
  1012. X            continue;
  1013. X        cand = klist[0];        /* No candidate now  */
  1014. X        r = 0;                    /* Current r-candidate  */
  1015. X        do {
  1016. X#ifdef  DEBUG
  1017. X            printf("a = %d, i = %d, b = %d\n", a, i, member[i]);
  1018. X#endif /* DEBUG */
  1019. X
  1020. X            /*
  1021. X             * Perform the merge algorithm 
  1022. X             */
  1023. X            if ((b = member[i]) < 0)
  1024. X                b = -b;
  1025. X#ifdef  DEBUG
  1026. X            printf("search(%d, %d, %d) -> %d\n",
  1027. X                   r, ktop, b, search(r, ktop, b));
  1028. X#endif /* DEBUG */
  1029. X            if ((s = search(r, ktop, b)) != 0) {
  1030. X                if (clist[klist[s]].b > b) {
  1031. X                    klist[r] = cand;
  1032. X                    r = s;
  1033. X                    cand = newcand(a, b, klist[s - 1]);
  1034. X#ifdef  DEBUG
  1035. X                    dumpklist(ktop, "klist[s-1]->b > b");
  1036. X#endif /* DEBUG */
  1037. X                }
  1038. X                if (s >= ktop) {
  1039. X                    klist[ktop + 1] = klist[ktop];
  1040. X                    ktop++;
  1041. X#ifdef  DEBUG
  1042. X                    klist[r] = cand;
  1043. X                    dumpklist(ktop, "extend");
  1044. X#endif /* DEBUG */
  1045. X                    break;
  1046. X                }
  1047. X            }
  1048. X        } while (member[++i] > 0);
  1049. X        klist[r] = cand;
  1050. X    }
  1051. X#ifdef  DEBUG
  1052. X    printf("last entry = %d\n", ktop - 1);
  1053. X#endif /* DEBUG */
  1054. X    return (ktop - 1);            /* Last entry found  */
  1055. X}
  1056. X
  1057. X
  1058. Xint
  1059. Xnewcand(a, b, pred)
  1060. X    int             a;            /* Line in fileA        */
  1061. X    int             b;            /* Line in fileB        */
  1062. X    int             pred;        /* Link to predecessor, index in cand[]  */
  1063. X{
  1064. X    register CANDIDATE *new;
  1065. X
  1066. X    clength++;
  1067. X    if (++clength >= csize) {
  1068. X        csize += CSIZE_INC;
  1069. X        clist = (CANDIDATE *) compact((char *) clist,
  1070. X                                      csize * sizeof(CANDIDATE),
  1071. X                                      "extending clist");
  1072. X    }
  1073. X    new = &clist[clength - 1];
  1074. X    new->a = a;
  1075. X    new->b = b;
  1076. X    new->link = pred;
  1077. X    return (clength - 1);
  1078. X}
  1079. X
  1080. X
  1081. X/*
  1082. X * Search klist[low..top] (inclusive) for b.  If klist[low]->b >= b,
  1083. X * return zero.  Else return s such that klist[s-1]->b < b and
  1084. X * klist[s]->b >= b.  Note that the algorithm presupposes the two
  1085. X * preset "fence" elements, (0, 0) and (slenA, slenB).
  1086. X */
  1087. X
  1088. Xsearch(low, high, b)
  1089. X    register unsigned low;
  1090. X    register unsigned high;
  1091. X    register int    b;
  1092. X{
  1093. X    register int    temp;
  1094. X    register unsigned mid;
  1095. X
  1096. X    if (clist[klist[low]].b >= b)
  1097. X        return (0);
  1098. X    while ((mid = (low + high) / 2) > low) {
  1099. X        if ((temp = clist[klist[mid]].b) > b)
  1100. X            high = mid;
  1101. X        else if (temp < b)
  1102. X            low = mid;
  1103. X        else {
  1104. X            return (mid);
  1105. X        }
  1106. X    }
  1107. X    return (mid + 1);
  1108. X}
  1109. X
  1110. X
  1111. Xunravel(k)
  1112. X    register int    k;
  1113. X{
  1114. X    register int    i;
  1115. X    register CANDIDATE *cp;
  1116. X    int             first_trailer;
  1117. X    int             difference;
  1118. X
  1119. X    first_trailer = lenA - suffix;
  1120. X    difference = lenB - lenA;
  1121. X#ifdef  DEBUG
  1122. X    printf("first trailer = %d, difference = %d\n",
  1123. X           first_trailer, difference);
  1124. X#endif /* DEBUG */
  1125. X    for (i = 0; i <= lenA; i++) {
  1126. X        match[i] = (i <= prefix) ? i
  1127. X            : (i > first_trailer) ? i + difference
  1128. X            : 0;
  1129. X    }
  1130. X#ifdef  DEBUG
  1131. X    printf("unravel\n");
  1132. X#endif /* DEBUG */
  1133. X    while (k != -1) {
  1134. X        cp = &clist[k];
  1135. X#ifdef  DEBUG
  1136. X        if (k < 0 || k >= clength)
  1137. X            error("Illegal link -> %d", k);
  1138. X        printf("match[%d] := %d\n", cp->a + prefix, cp->b + prefix);
  1139. X#endif /* DEBUG */
  1140. X        match[cp->a + prefix] = cp->b + prefix;
  1141. X        k = cp->link;
  1142. X    }
  1143. X}
  1144. X
  1145. X
  1146. X/*
  1147. X * Check for hash matches (jackpots) and collect random access indices to
  1148. X * the two files.
  1149. X *
  1150. X * It should be possible to avoid doing most of the ftell's by noticing
  1151. X * that we are not doing a context diff and noticing that if a line
  1152. X * compares equal to the other file, we will not ever need to know its
  1153. X * file position.  FIXME.
  1154. X */
  1155. X
  1156. Xcheck(fileAname, fileBname)
  1157. X    char           *fileAname;
  1158. X    char           *fileBname;
  1159. X{
  1160. X    register int    a;            /* Current line in file A  */
  1161. X    register int    b;            /* Current line in file B  */
  1162. X    int             jackpot;
  1163. X
  1164. X/*
  1165. X * The VAX C ftell() returns the address of the CURRENT record, not the
  1166. X * next one (as in DECUS C or, effectively, other C's).  Hence, the values
  1167. X * are "off by one" in the array.  OFFSET compensates for this.
  1168. X */
  1169. X
  1170. X#ifdef vms
  1171. X#define OFFSET (-1)
  1172. X#else /* !vms */
  1173. X#define OFFSET 0
  1174. X#endif /* vms */
  1175. X
  1176. X    b = 1;
  1177. X    rewind(infd[0]);
  1178. X    rewind(infd[1]);
  1179. X/*
  1180. X * See above; these would be over-written on VMS anyway.
  1181. X */
  1182. X
  1183. X#ifndef vms
  1184. X    oldseek[0] = ftell(infd[0]);
  1185. X    newseek[0] = ftell(infd[1]);
  1186. X#endif /* vms */
  1187. X
  1188. X    jackpot = 0;
  1189. X#ifdef  DEBUG
  1190. X    printf("match vector\n");
  1191. X    for (a = 0; a <= lenA; a++)
  1192. X        printf("match[%d] = %d\n", a, match[a]);
  1193. X#endif /* DEBUG */
  1194. X    for (a = 1; a <= lenA; a++) {
  1195. X        if (match[a] == 0) {
  1196. X            /* Unique line in A */
  1197. X            oldseek[a + OFFSET] = ftell(infd[0]);
  1198. X            getline(infd[0], text);
  1199. X            continue;
  1200. X        }
  1201. X        while (b < match[a]) {
  1202. X            /* Skip over unique lines in B */
  1203. X            newseek[b + OFFSET] = ftell(infd[1]);
  1204. X            getline(infd[1], textb);
  1205. X            b++;
  1206. X        }
  1207. X
  1208. X        /*
  1209. X         * Compare the two, supposedly matching, lines. Unless we are going
  1210. X         * to print these lines, don't bother to remember where they are.  We
  1211. X         * only print matching lines if a context diff is happening, or if a
  1212. X         * jackpot occurs. 
  1213. X         */
  1214. X        if (cflag) {
  1215. X            oldseek[a + OFFSET] = ftell(infd[0]);
  1216. X            newseek[b + OFFSET] = ftell(infd[1]);
  1217. X        }
  1218. X        getline(infd[0], text);
  1219. X        getline(infd[1], textb);
  1220. X        if (!streq(text, textb)) {
  1221. X            fprintf(stderr, "Spurious match:\n");
  1222. X            fprintf(stderr, "line %d in %s, \"%s\"\n",
  1223. X                    a, fileAname, text);
  1224. X            fprintf(stderr, "line %d in %s, \"%s\"\n",
  1225. X                    b, fileBname, textb);
  1226. X            match[a] = 0;
  1227. X            jackpot++;
  1228. X        }
  1229. X        b++;
  1230. X    }
  1231. X    for (; b <= lenB; b++) {
  1232. X        newseek[b + OFFSET] = ftell(infd[1]);
  1233. X        getline(infd[1], textb);
  1234. X    }
  1235. X/*
  1236. X * The logical converse to the code up above, for NON-VMS systems, to
  1237. X * store away an fseek() pointer at the beginning of the file.  For VMS,
  1238. X * we need one at EOF...
  1239. X */
  1240. X
  1241. X#ifdef vms
  1242. X    oldseek[lenA] = ftell(infd[0]);
  1243. X    getline(infd[0], text);        /* Will hit EOF...  */
  1244. X    newseek[lenB] = ftell(infd[1]);
  1245. X    getline(infd[1], textb);    /* Will hit EOF...  */
  1246. X#endif /* vms */
  1247. X
  1248. X    return (jackpot);
  1249. X}
  1250. X
  1251. X
  1252. Xoutput(fileAname, fileBname)
  1253. X    char           *fileAname, *fileBname;
  1254. X{
  1255. X    register int    astart;
  1256. X    register int    aend = 0;
  1257. X    int             bstart;
  1258. X    register int    bend;
  1259. X
  1260. X    rewind(infd[0]);
  1261. X    rewind(infd[1]);
  1262. X    match[0] = 0;
  1263. X    match[lenA + 1] = lenB + 1;
  1264. X    if (!eflag) {
  1265. X        if (cflag) {
  1266. X
  1267. X            /*
  1268. X             * Should include ctime style dates after the file names, but
  1269. X             * this would be non-trivial on OSK.  Perhaps there should be a
  1270. X             * special case for stdin. 
  1271. X             */
  1272. X            printf("*** %s\n--- %s\n", fileAname, fileBname);
  1273. X        }
  1274. X
  1275. X        /*
  1276. X         * Normal printout 
  1277. X         */
  1278. X        for (astart = 1; astart <= lenA; astart = aend + 1) {
  1279. X
  1280. X            /*
  1281. X             * New subsequence, skip over matching stuff 
  1282. X             */
  1283. X            while (astart <= lenA
  1284. X                   && match[astart] == (match[astart - 1] + 1))
  1285. X                astart++;
  1286. X
  1287. X            /*
  1288. X             * Found a difference, setup range and print it 
  1289. X             */
  1290. X            bstart = match[astart - 1] + 1;
  1291. X            aend = astart - 1;
  1292. X            while (aend < lenA && match[aend + 1] == 0)
  1293. X                aend++;
  1294. X            bend = match[aend + 1] - 1;
  1295. X            match[aend] = bend;
  1296. X            change(astart, aend, bstart, bend);
  1297. X        }
  1298. X    } else {
  1299. X
  1300. X        /*
  1301. X         * Edit script output -- differences are output "backwards" for the
  1302. X         * benefit of a line-oriented editor. 
  1303. X         */
  1304. X        for (aend = lenA; aend >= 1; aend = astart - 1) {
  1305. X            while (aend >= 1
  1306. X                   && match[aend] == (match[aend + 1] - 1)
  1307. X                   && match[aend] != 0)
  1308. X                aend--;
  1309. X            bend = match[aend + 1] - 1;
  1310. X            astart = aend + 1;
  1311. X            while (astart > 1 && match[astart - 1] == 0)
  1312. X                astart--;
  1313. X            bstart = match[astart - 1] + 1;
  1314. X            match[astart] = bstart;
  1315. X            change(astart, aend, bstart, bend);
  1316. X        }
  1317. X    }
  1318. X    if (lenA == 0)
  1319. X        change(1, 0, 1, lenB);
  1320. X}
  1321. X
  1322. X
  1323. X/*
  1324. X * Output a change entry: fileA[astart..aend] changed to fileB[bstart..bend]
  1325. X */
  1326. X
  1327. Xchange(astart, aend, bstart, bend)
  1328. X    int             astart;
  1329. X    int             aend;
  1330. X    int             bstart;
  1331. X    int             bend;
  1332. X{
  1333. X    char            c;
  1334. X
  1335. X    /*
  1336. X     * This catches a "dummy" last entry 
  1337. X     */
  1338. X    if (astart > aend && bstart > bend)
  1339. X        return;
  1340. X    c = (astart > aend) ? 'a' : (bstart > bend) ? 'd' : 'c';
  1341. X    if (cflag)
  1342. X        fputs("**************\n*** ", stdout);
  1343. X
  1344. X    if (c == 'a' && !cflag)
  1345. X        range(astart - 1, astart - 1, 0);        /* Addition: just print one
  1346. X                                                 * odd # */
  1347. X    else
  1348. X        range(astart, aend, 0);    /* Print both, if different */
  1349. X    if (!cflag) {
  1350. X        putchar(c);
  1351. X        if (!eflag) {
  1352. X            if (c == 'd')
  1353. X                range(bstart - 1, bstart - 1, 1);        /* Deletion: just print
  1354. X                                                         * one odd # */
  1355. X            else
  1356. X                range(bstart, bend, 1);    /* Print both, if different */
  1357. X        }
  1358. X    }
  1359. X    putchar('\n');
  1360. X    if ((!eflag && c != 'a') || cflag) {
  1361. X        fetch(oldseek, astart, aend, lenA, infd[0],
  1362. X              cflag ? (c == 'd' ? "- " : "! ") : "< ");
  1363. X        if (cflag) {
  1364. X            fputs("--- ", stdout);
  1365. X            range(bstart, bend, 1);
  1366. X            fputs(" -----\n", stdout);
  1367. X        } else if (astart <= aend && bstart <= bend)
  1368. X            printf("---\n");
  1369. X    }
  1370. X    fetch(newseek, bstart, bend, lenB, infd[1],
  1371. X          cflag ? (c == 'a' ? "+ " : "! ") : (eflag ? "" : "> "));
  1372. X    if (eflag && bstart <= bend)
  1373. X        printf(".\n");
  1374. X}
  1375. X
  1376. X
  1377. X/*
  1378. X * Print a range
  1379. X */
  1380. X
  1381. Xrange(from, to, w)
  1382. X    int             from;
  1383. X    int             to;
  1384. X    int             w;
  1385. X{
  1386. X    if (cflag) {
  1387. X        if ((from -= cflag) <= 0)
  1388. X            from = 1;
  1389. X        if ((to += cflag) > len[w])
  1390. X            to = len[w];
  1391. X    }
  1392. X    if (to > from) {
  1393. X        printf("%d,%d", from, to);
  1394. X    } else if (to < from) {
  1395. X        printf("%d,%d", to, from);
  1396. X    } else {
  1397. X        printf("%d", from);
  1398. X    }
  1399. X}
  1400. X
  1401. X
  1402. X/*
  1403. X * Print the appropriate text
  1404. X */
  1405. X
  1406. Xfetch(seekvec, start, end, trueend, fd, pfx)
  1407. X    long           *seekvec;
  1408. X    register int    start;
  1409. X    register int    end;
  1410. X    int             trueend;
  1411. X    FILE           *fd;
  1412. X    char           *pfx;
  1413. X{
  1414. X    register int    i;
  1415. X    register int    first;
  1416. X    register int    last;
  1417. X
  1418. X    if (cflag) {
  1419. X        if ((first = start - cflag) <= 0)
  1420. X            first = 1;
  1421. X        if ((last = end + cflag) > trueend)
  1422. X            last = trueend;
  1423. X    } else {
  1424. X        first = start;
  1425. X        last = end;
  1426. X    }
  1427. X    if (fseek(fd, seekvec[first], 0) != 0) {
  1428. X        printf("?Can't read line %d at %08lx (hex) in file%c\n",
  1429. X               start, seekvec[first],
  1430. X               (fd == infd[0]) ? 'A' : 'B');
  1431. X    } else {
  1432. X        for (i = first; i <= last; i++) {
  1433. X            if (fgetss(text, sizeof text, fd) == NULL) {
  1434. X                printf("** Unexpected end of file\n");
  1435. X                break;
  1436. X            }
  1437. X#ifdef DEBUG
  1438. X            printf("%5d: %s%s\n", i, pfx, text);
  1439. X#else /* !DEBUG */
  1440. X            fputs((cflag && (i < start || i > end)) ? "  " : pfx, stdout);
  1441. X            fputs(text, stdout);
  1442. X            putchar('\n');
  1443. X#endif /* DEBUG */
  1444. X        }
  1445. X    }
  1446. X}
  1447. X
  1448. X
  1449. X/*
  1450. X * Input routine, read one line to buffer[], return TRUE on eof, else FALSE.
  1451. X * The terminating newline is always removed.  If "-b" was given, trailing
  1452. X * whitespace (blanks and tabs) are removed and strings of blanks and
  1453. X * tabs are replaced by a single blank.  Getline() does all hacking for
  1454. X * redirected input files.
  1455. X */
  1456. X
  1457. Xint
  1458. Xgetline(fd, buffer)
  1459. X    FILE           *fd;
  1460. X    char           *buffer;
  1461. X{
  1462. X    register char  *top;
  1463. X    register char  *fromp;
  1464. X    register char   c;
  1465. X
  1466. X    if (fgetss(buffer, sizeof text, fd) == NULL) {
  1467. X        *buffer = EOS;
  1468. X        return (TRUE);
  1469. X    }
  1470. X    if (fd == stdin)
  1471. X        fputss(buffer, tempfd);
  1472. X    if (bflag || iflag) {
  1473. X        top = buffer;
  1474. X        fromp = buffer;
  1475. X        while ((c = *fromp++) != EOS) {
  1476. X            if (bflag && (c == ' ' || c == '\t')) {
  1477. X                c = ' ';
  1478. X                while (*fromp == ' ' || *fromp == '\t')
  1479. X                    fromp++;
  1480. X            }
  1481. X            if (iflag)
  1482. X                c = tolower(c);
  1483. X            *top++ = c;
  1484. X        }
  1485. X        if (bflag && top[-1] == ' ')
  1486. X            top--;
  1487. X        *top = EOS;
  1488. X    }
  1489. X    return (FALSE);
  1490. X}
  1491. X
  1492. X
  1493. Xstatic unsigned short crc16a[] = {
  1494. X                                  0000000, 0140301, 0140601, 0000500,
  1495. X                                  0141401, 0001700, 0001200, 0141101,
  1496. X                                  0143001, 0003300, 0003600, 0143501,
  1497. X                                  0002400, 0142701, 0142201, 0002100,
  1498. X};
  1499. X
  1500. Xstatic unsigned short crc16b[] = {
  1501. X                                  0000000, 0146001, 0154001, 0012000,
  1502. X                                  0170001, 0036000, 0024000, 0162001,
  1503. X                                  0120001, 0066000, 0074000, 0132001,
  1504. X                                  0050000, 0116001, 0104001, 0043000,
  1505. X};
  1506. X
  1507. X
  1508. X/*
  1509. X * Return the CRC16 hash code for the buffer
  1510. X * Algorithm from Stu Wecker (Digital memo 130-959-002-00).
  1511. X */
  1512. X
  1513. Xunsigned short
  1514. Xhash(buffer)
  1515. X    char           *buffer;
  1516. X{
  1517. X    register unsigned short crc;
  1518. X    register char  *tp;
  1519. X    register short  temp;
  1520. X
  1521. X    crc = 0;
  1522. X    for (tp = buffer; *tp != EOS;) {
  1523. X        temp = *tp++ ^ crc;        /* XOR crc with new char  */
  1524. X        crc = (crc >> 8)
  1525. X            ^ crc16a[(temp & 0017)]
  1526. X            ^ crc16b[(temp & 0360) >> 4];
  1527. X    }
  1528. X#ifdef  DEBUG_ALL
  1529. X    printf("%06o: %s\n", (crc == 0) ? 1 : crc, buffer);
  1530. X#endif /* DEBUG_ALL */
  1531. X    return ((crc == 0) ? (unsigned short) 1 : crc);
  1532. X}
  1533. X
  1534. X
  1535. X#ifdef vms
  1536. Xopendir(which, arg, okfd)
  1537. X    int             which;        /* Which file to open (0 or 1)       */
  1538. X    char          **arg;        /* File name argument, &argv[which]  */
  1539. X    FILE           *okfd;        /* File name (already open)       */
  1540. X{
  1541. X    register char  *tp;
  1542. X    register int    c;
  1543. X    register char  *newname;
  1544. X
  1545. X    fgetname(okfd, text);
  1546. X
  1547. X    /*
  1548. X     * Skip over device name 
  1549. X     */
  1550. X    for (tp = text; (c = *tp) && c != ':'; tp++);
  1551. X    if (c)
  1552. X        tp++;
  1553. X    else
  1554. X        tp = text;
  1555. X
  1556. X    /*
  1557. X     * Skip over [UIC] or [PPN] if present 
  1558. X     */
  1559. X    if (*tp == '[' || *tp == '(') {
  1560. X        while ((c = *tp++) && c != ']' && c != ')');
  1561. X        if (c == 0) {
  1562. X            fprintf(stderr, "?Bug: bad file name \"%s\"\n",
  1563. X                    text);
  1564. X            tp--;
  1565. X        }
  1566. X    }
  1567. X    strcpy(text, tp);
  1568. X
  1569. X    /*
  1570. X     * Don't include version 
  1571. X     */
  1572. X    for (tp = text; (c = *tp) && c != ';'; tp++);
  1573. X    *tp = 0;
  1574. X
  1575. X    /*
  1576. X     * Now, text has the file name, tp - text, its length, and *arg the
  1577. X     * (possible) directory name.  Create a new file name for opening. 
  1578. X     */
  1579. X#ifndef    OSK
  1580. X    if ((newname = malloc(tp - text + strlen(*arg) + 1)) == NULL)
  1581. X        error("Out of space at start");
  1582. X#ifdef    AMIGA
  1583. X    savsiz = tp - text + strlen(*arg) + 1;
  1584. X    savptr = newname;
  1585. X#endif /* AMIGA */
  1586. X#else /* OSK */
  1587. X    newname = myalloc(tp - text + strlen(*arg) + 1, "Out of space at start");
  1588. X#endif /* OSK */
  1589. X    concat(newname, *arg, text, NULL);
  1590. X    if ((infd[which] = fopen(newname, "r")) == NULL)
  1591. X        cant(*arg, "constructed input", 1);
  1592. X    else
  1593. X        *arg = newname;
  1594. X}
  1595. X/* Amiga C doesn't have all these extensions for directory... */
  1596. X#endif /* vms */
  1597. X
  1598. X
  1599. X/*
  1600. X * Allocate or crash.
  1601. X */
  1602. X
  1603. Xchar           *
  1604. Xmyalloc(amount, why)
  1605. X    unsigned        amount;
  1606. X    char           *why;
  1607. X{
  1608. X    register char  *pointer;
  1609. X
  1610. X#ifdef OSK
  1611. X    amount += sizeof(int);
  1612. X#endif /* OSK */
  1613. X    if ((pointer = malloc((unsigned) amount)) == NULL)
  1614. X        noroom(why);
  1615. X#ifdef OSK
  1616. X    *((int *) pointer) = amount;
  1617. X    pointer += sizeof(int);
  1618. X#ifdef DEBUG
  1619. X    fprintf(stderr, "Myalloc: %d at %06o\n", amount, pointer);
  1620. X#endif /* DEBUG */
  1621. X#endif /* OSK */
  1622. X#ifdef    AMIGA
  1623. X    savsiz = amount;
  1624. X    savptr = pointer;
  1625. X#endif /* AMIGA */
  1626. X
  1627. X    return (pointer);
  1628. X}
  1629. X
  1630. X
  1631. X/*
  1632. X * Reallocate pointer, compacting storage
  1633. X *
  1634. X * The "compacting storage" part is probably not relevant any more.
  1635. X * There used to be horrid code here that malloc'd one byte and freed
  1636. X * it at magic times, to cause garbage collection of the freespace
  1637. X * or something.  It's safely gone now, you didn't have to see it.
  1638. X *    -- John Gilmore, Nebula Consultants, Sept 26, 1986
  1639. X */
  1640. X
  1641. Xchar           *
  1642. Xcompact(pointer, new_amount, why)
  1643. X    char           *pointer;
  1644. X    unsigned        new_amount;
  1645. X    char           *why;
  1646. X{
  1647. X    register char  *new_pointer;
  1648. X
  1649. X#ifndef AMIGA
  1650. X#ifndef OSK
  1651. X#ifdef TURBO
  1652. X    extern void    *realloc();
  1653. X#else /* !TURBO */
  1654. X    extern char    *realloc();
  1655. X#endif /* TURBO */
  1656. X
  1657. X    if ((new_pointer = realloc(pointer, (unsigned) new_amount)) == NULL) {
  1658. X        noroom(why);
  1659. X    }
  1660. X#else /* OSK */
  1661. X    register int    old_amount;
  1662. X    new_amount += sizeof(int);
  1663. X    if ((new_pointer = malloc(new_amount)) == NULL)
  1664. X        noroom(why);
  1665. X    *(int *) new_pointer = new_amount;
  1666. X    new_pointer += sizeof(int);
  1667. X    old_amount = *(((int *) pointer) - 1);
  1668. X    /* _strass is like bcopy with the first two arguments reversted */
  1669. X    _strass(new_pointer, pointer, (new_amount <= old_amount ?
  1670. X                                   new_amount : old_amount) - sizeof(int));
  1671. X#ifdef DEBUG
  1672. X    fprintf(stderr, "compact %d to %d from %06o to %06o\n",
  1673. X            old_amount, new_amount, pointer, new_pointer);
  1674. X#endif /* DEBUG */
  1675. X    free(pointer - sizeof(int));
  1676. X#endif /* OSK */
  1677. X#else /* AMIGA */
  1678. X
  1679. X    /*
  1680. X     * This routine is heavily dependent on C storage allocator hacks For
  1681. X     * Amiga, we can't rely on storage being left alone "up to" the boundary
  1682. X     * of allocation as in VMS or RSX. Therefore we have to be different here
  1683. X     * and allocate a new larger segment, then free the old one. Messy but
  1684. X     * hopefully it will work. 
  1685. X     */
  1686. X    extern char    *malloc();
  1687. X
  1688. X    /* No realloc().  Do a malloc and copy it.  */
  1689. X    if ((new_pointer = malloc((unsigned) new_amount)) == NULL) {
  1690. X        noroom(why);
  1691. X    }
  1692. X  /* This MUST assume the program calls compact using the old pointer as the
  1693. X  last call of malloc... Reason is that RSX version is really simpleminded */
  1694. X    cpysiz = savsiz;
  1695. X  /* Complain if deallocate area not same as last allocate area */
  1696. X    if (savptr != pointer)
  1697. X        bogus(why);
  1698. X    wrk2 = new_pointer;
  1699. X    for (wrk = pointer; cpysiz > 0; cpysiz--) {
  1700. X  /* copy data to new area */
  1701. X        *wrk2++ = *wrk++;
  1702. X    }
  1703. X  /* when done, free old memory area. */
  1704. X    free(pointer);
  1705. X#endif /* AMIGA */
  1706. X
  1707. X#ifndef OSK
  1708. X#ifdef  DEBUG
  1709. X    if (new_pointer != pointer) {
  1710. X        fprintf(stderr, "moved from %06o to %06o\n",
  1711. X                pointer, new_pointer);
  1712. X    }
  1713. X/*  rdump(new_pointer, why);
  1714. X*/
  1715. X#endif /* DEBUG */
  1716. X#endif /* OSK */
  1717. X    return (new_pointer);
  1718. X}
  1719. X
  1720. X
  1721. Xnoroom(why)
  1722. X    char           *why;
  1723. X{
  1724. X    fprintf(stderr, "?DIFF-F-out of room when %s\n", why);
  1725. X    exit(IO_ERROR);
  1726. X}
  1727. X
  1728. X
  1729. X#ifdef    AMIGA
  1730. Xbogus(why)
  1731. X    char           *why;
  1732. X{
  1733. X    fprintf(stderr, "?DIFF-F-invalid compaction when %s\n", why);
  1734. X    exit(IO_ERROR);
  1735. X}
  1736. X#endif    /* AMIGA */
  1737. X
  1738. X
  1739. X#ifdef  DEBUG
  1740. X/*
  1741. X * Dump memory block
  1742. X */
  1743. X
  1744. Xrdump(pointer, why)
  1745. X    int            *pointer;
  1746. X    char           *why;
  1747. X{
  1748. X    int            *last;
  1749. X    int             count;
  1750. X
  1751. X    last = ((int **) pointer)[-1];
  1752. X    fprintf(stderr, "dump %s of %06o -> %06o, %d words",
  1753. X            why, pointer, last, last - pointer);
  1754. X    last = (int *) (((int) last) & ~1);
  1755. X    for (count = 0; pointer < last; ++count) {
  1756. X        if ((count & 07) == 0) {
  1757. X            fprintf(stderr, "\n%06o", pointer);
  1758. X        }
  1759. X        fprintf(stderr, "\t%06o", *pointer);
  1760. X        pointer++;
  1761. X    }
  1762. X    fprintf(stderr, "\n");
  1763. X}
  1764. X#endif /* DEBUG */
  1765. X
  1766. X
  1767. X/*
  1768. X * Can't open file message
  1769. X */
  1770. X
  1771. Xcant(filename, what, fatalflag)
  1772. X    char           *filename;
  1773. X    char           *what;
  1774. X    int             fatalflag;
  1775. X{
  1776. X    fprintf(stderr, "Can't open %s file \"%s\": ", what, filename);
  1777. X#ifndef    OSK
  1778. X    perror((char *) NULL);
  1779. X#else
  1780. X    prerr(0, errno);
  1781. X#endif
  1782. X    if (fatalflag) {
  1783. X        exit(fatalflag);
  1784. X    }
  1785. X}
  1786. X
  1787. X
  1788. X#ifdef  DEBUG
  1789. Xdump(d_linep, d_len, d_which)
  1790. X    LINE           *d_linep;
  1791. X    int                d_len;
  1792. X    int                d_which;
  1793. X{
  1794. X    register int    i;
  1795. X
  1796. X    printf("Dump of file%c, %d elements\n", "AB"[d_which], d_len);
  1797. X    printf("linep @ %06o\n", d_linep);
  1798. X    for (i = 0; i <= d_len; i++) {
  1799. X        printf("%3d  %6d  %06o\n", i,
  1800. X               d_linep[i].serial, d_linep[i].hash);
  1801. X    }
  1802. X}
  1803. X
  1804. X
  1805. X/*
  1806. X * Dump klist
  1807. X */
  1808. X
  1809. Xdumpklist(kmax, why)
  1810. X    int             kmax;
  1811. X    char           *why;
  1812. X{
  1813. X    register int    i;
  1814. X    register CANDIDATE *cp;
  1815. X    register int    count;
  1816. X
  1817. X    printf("\nklist[0..%d] %s, clength = %d\n", kmax, why, clength);
  1818. X    for (i = 0; i <= kmax; i++) {
  1819. X        cp = &clist[klist[i]];
  1820. X        printf("%2d %2d", i, klist[i]);
  1821. X        if (cp >= &clist[0] && cp < &clist[clength])
  1822. X            printf(" (%2d %2d -> %2d)\n", cp->a, cp->b, cp->link);
  1823. X        else if (klist[i] == -1)
  1824. X            printf(" End of chain\n");
  1825. X        else
  1826. X            printf(" illegal klist element\n");
  1827. X    }
  1828. X    for (i = 0; i <= kmax; i++) {
  1829. X        count = -1;
  1830. X        for (cp = (CANDIDATE *) klist[i]; cp > &clist[0];
  1831. X             cp = (CANDIDATE *) & cp->link) {
  1832. X            if (++count >= 6) {
  1833. X                printf("\n    ");
  1834. X                count = 0;
  1835. X            }
  1836. X            printf(" (%2d: %2d,%2d -> %d)",
  1837. X                   cp - clist, cp->a, cp->b, cp->link);
  1838. X        }
  1839. X        printf("\n");
  1840. X    }
  1841. X    printf("*\n");
  1842. X}
  1843. X#endif    /* DEBUG */
  1844. X
  1845. X
  1846. X
  1847. X#ifdef  TIMING
  1848. X
  1849. X/*
  1850. X * Dump time buffer
  1851. X */
  1852. X
  1853. Xptime(why)
  1854. X    char           *why;
  1855. X{
  1856. X    long            ttemp;
  1857. X
  1858. X    ttemp = time(NULL);
  1859. X    printf("%ld seconds for %s\n",
  1860. X           ttemp - sectiontime, why);
  1861. X    sectiontime = ttemp;
  1862. X}
  1863. X#endif    /* TIMING */
  1864. X
  1865. X
  1866. X/*
  1867. X * TRUE if strings are identical
  1868. X */
  1869. X
  1870. Xint
  1871. Xstreq(s1, s2)
  1872. X    register char  *s1;
  1873. X    register char  *s2;
  1874. X{
  1875. X    while (*s1++ == *s2) {
  1876. X        if (*s2++ == EOS)
  1877. X            return (TRUE);
  1878. X    }
  1879. X    return (FALSE);
  1880. X}
  1881. X
  1882. X
  1883. X/*
  1884. X * Error message before retiring.
  1885. X */
  1886. X
  1887. X/* VARARGS */
  1888. Xerror(format, args)
  1889. X    char           *format;
  1890. X{
  1891. X    fprintf(stderr, format, &args);
  1892. X    putc('\n', stderr);
  1893. X    _error();
  1894. X}
  1895. X
  1896. X
  1897. X_error()
  1898. X{
  1899. X    exit(1);
  1900. X}
  1901. X
  1902. X
  1903. X/*
  1904. X * Like fput() except that it puts a newline at the end of the line.
  1905. X */
  1906. X
  1907. Xfputss(s, iop)
  1908. X    register char  *s;
  1909. X    register FILE  *iop;
  1910. X{
  1911. X    fputs(s, iop);
  1912. X    putc('\n', iop);
  1913. X}
  1914. X
  1915. X
  1916. X/*
  1917. X * Fgetss() is like fgets() except that the terminating newline
  1918. X * is removed. 
  1919. X */
  1920. X
  1921. Xchar           *
  1922. Xfgetss(s, n, iop)
  1923. X    char           *s;
  1924. X    register FILE  *iop;
  1925. X{
  1926. X    register char  *cs;
  1927. X
  1928. X    if (fgets(s, n, iop) == NULL)
  1929. X        return ((char *) NULL);
  1930. X    cs = s + strlen(s) - 1;
  1931. X    if (*cs == '\n')
  1932. X        *cs = '\0';
  1933. X    return (s);
  1934. X}
  1935. END_OF_diff.c
  1936. if test 33595 -ne `wc -c <diff.c`; then
  1937.     echo shar: \"diff.c\" unpacked with wrong size!
  1938. fi
  1939. # end of overwriting check
  1940. fi
  1941. if test -f diff.doc -a "${1}" != "-c" ; then 
  1942.   echo shar: Will not over-write existing file \"diff.doc\"
  1943. else
  1944. echo shar: Extracting \"diff.doc\" \(6151 characters\)
  1945. sed "s/^X//" >diff.doc <<'END_OF_diff.doc'
  1946. X
  1947. X
  1948. X
  1949. X     CCCCDDDDIIIIFFFFFFFF((((1111))))                    UUUUNNNNIIIIXXXX 5555....0000                     CCCCDDDDIIIIFFFFFFFF((((1111))))
  1950. X
  1951. X
  1952. X
  1953. X     NNNNAAAAMMMMEEEE
  1954. X          cdiff - Public Domain cdiff (context diff) program
  1955. X
  1956. X     SSSSYYYYNNNNOOOOPPPPSSSSIIIISSSS
  1957. X          ddddiiiiffffffff [ ----bbbb ----cccc ----iiii ----eeee ] file1 file2
  1958. X
  1959. X     DDDDEEEESSSSCCCCRRRRIIIIPPPPTTTTIIIIOOOONNNN
  1960. X          _D_i_f_f compares two files, showing what must be changed to
  1961. X          make them identical. Either file1 or file2 (but not both)
  1962. X          may refer to directories. If that is the case, a file in the
  1963. X          directory whose name is the same as the other file argument
  1964. X          will be used. The standard input may be used for one of the
  1965. X          files by replacing the argument by "-". Except for the
  1966. X          standard input, both files must be on disk devices.
  1967. X
  1968. X     OOOOPPPPTTTTIIIIOOOONNNNSSSS
  1969. X          ----bbbb Remove trailing whitespace (blanks and tabs) and compress
  1970. X               all other strings of whitespace to a single blank.
  1971. X
  1972. X          ----cccc Print some context -- matching lines before and after the
  1973. X               non-match section.  Mark non-matched sections with "|".
  1974. X
  1975. X          ----iiii Ignore lower/upper case distinctions.
  1976. X
  1977. X          ----eeee Output is in an "editor script" format which is
  1978. X               compatible with the Unix 'ed' editor.
  1979. X
  1980. X          All information needed to compare the files is maintained in
  1981. X          main memory. This means that very large files (or fairly
  1982. X          large files with many differences) will cause the program to
  1983. X          abort with an "out of space" message. Main memory
  1984. X          requirements (in words) are approximately:
  1985. X
  1986. X                    2 * (length of file1 + length of file2)
  1987. X                           + 3 * (number of changes)
  1988. X
  1989. X          (Where "length" is the number of lines of data in each
  1990. X          file.)
  1991. X
  1992. X          The algorithm reads each file twice, once to build hash
  1993. X          tables and once to check for fortuitous matches (two lines
  1994. X          that are in fact different, but which have the same hash
  1995. X          value). CPU time requirements include sorting the hash
  1996. X          tables and randomly searching memory tables for equivalence
  1997. X          classes. For example, on a time-shared VAX-11/780, comparing
  1998. X          two 1000 line files required about 30 seconds (elapsed clock
  1999. X          time) and about 10,000 bytes of working storage. About 90
  2000. X          per-cent of the time was taken up by file I/O.
  2001. X
  2002. X     DDDDIIIIAAAAGGGGNNNNOOOOSSSSTTTTIIIICCCCSSSS
  2003. X          Warning, bad option 'x'
  2004. X               The option is ignored.
  2005. X
  2006. X
  2007. X
  2008. X     Page 1                                          (printed 1/13/88)
  2009. X
  2010. X
  2011. X
  2012. X
  2013. X
  2014. X
  2015. X     CCCCDDDDIIIIFFFFFFFF((((1111))))                    UUUUNNNNIIIIXXXX 5555....0000                     CCCCDDDDIIIIFFFFFFFF((((1111))))
  2016. X
  2017. X
  2018. X
  2019. X          Usage ...
  2020. X               Two input files were not specified.
  2021. X
  2022. X          Can't open input file "filename".
  2023. X               Can't continue.
  2024. X
  2025. X          Out of space
  2026. X               The program ran out of memory while comparing the two
  2027. X               files.
  2028. X
  2029. X          Can't read line nnn at xxx in file[A/B]
  2030. X               This indicates an I/O error when seeking to the
  2031. X               specific line.  It should not happen.
  2032. X
  2033. X          Spurious match, output is not optimal.
  2034. X               Two lines that were different yielded the same hash
  2035. X               value.  This is harmless except that the difference
  2036. X               output is not the minimum set of differences between
  2037. X               the two files.  For example, instead of the output:
  2038. X                          lines 1 to 5 were changed to ...
  2039. X               the program will print
  2040. X                          lines 1 to 3 were changed to ...
  2041. X                          lines 4 to 5 were changed to ...
  2042. X
  2043. X          The program uses a CRC16 hash code.
  2044. X               The likelihood of this error is quite small.
  2045. X
  2046. X     AAAAUUUUTTTTHHHHOOOORRRR
  2047. X          The diff algorithm was developed by J. W. Hunt and M. D.
  2048. X          McIlroy, using a central algorithm defined by H. S. Stone.
  2049. X          It was published in:
  2050. X               Hunt, J. W., and McIlroy, M. D.,
  2051. X               An Algorithm for Differential File Comparison,
  2052. X               Computing Science Technical Report #41,
  2053. X               Bell Laboratories, Murray Hill, NJ  07974
  2054. X
  2055. X     BBBBUUUUGGGGSSSS
  2056. X          On RSX and DECUS C on VMS systems, diff may fail if the both
  2057. X          files are not "variable-length, implied carriage control"
  2058. X          format.  The scopy program can be used to convert files to
  2059. X          this format if problems arise.
  2060. X
  2061. X          When compiled under VAX C, diff handles STREAM_LF files
  2062. X          properly (in addition to the canonical variable-length
  2063. X          implied carriage control files). Other variations should
  2064. X          work, but have not been tested.
  2065. X
  2066. X          When compiled under VAX C, diff is quite slow for unknown
  2067. X          reasons which ought to be investigated. On the other hand,
  2068. X          it has access to effectively unlimited memory.
  2069. X
  2070. X          Output in a form suitable for ed - the -e option - seems
  2071. X
  2072. X
  2073. X
  2074. X     Page 2                                          (printed 1/13/88)
  2075. X
  2076. X
  2077. X
  2078. X
  2079. X
  2080. X
  2081. X     CCCCDDDDIIIIFFFFFFFF((((1111))))                    UUUUNNNNIIIIXXXX 5555....0000                     CCCCDDDDIIIIFFFFFFFF((((1111))))
  2082. X
  2083. X
  2084. X
  2085. X          rather pointless; the analogue on DEC systems is SLP (SUMSLP
  2086. X          on VMS). It would be simple to provide SLP-compatible
  2087. X          output. The question is, why bother - since the various DEC
  2088. X          file comparisonFound 424 control chars in "diff.doc"
  2089.  utilities already produce it.
  2090. X
  2091. X
  2092. X
  2093. X
  2094. X
  2095. X
  2096. X
  2097. X
  2098. X
  2099. X
  2100. X
  2101. X
  2102. X
  2103. X
  2104. X
  2105. X
  2106. X
  2107. X
  2108. X
  2109. X
  2110. X
  2111. X
  2112. X
  2113. X
  2114. X
  2115. X
  2116. X
  2117. X
  2118. X
  2119. X
  2120. X
  2121. X
  2122. X
  2123. X
  2124. X
  2125. X
  2126. X
  2127. X
  2128. X
  2129. X
  2130. X
  2131. X
  2132. X
  2133. X
  2134. X
  2135. X
  2136. X
  2137. X
  2138. X
  2139. X
  2140. X
  2141. X     Page 3                                          (printed 1/13/88)
  2142. X
  2143. X
  2144. X
  2145. END_OF_diff.doc
  2146. echo shar: 424 control characters may be missing from \"diff.doc\"
  2147. if test 6151 -ne `wc -c <diff.doc`; then
  2148.     echo shar: \"diff.doc\" unpacked with wrong size!
  2149. fi
  2150. # end of overwriting check
  2151. fi
  2152. if test -f diff.mem -a "${1}" != "-c" ; then 
  2153.   echo shar: Will not over-write existing file \"diff.mem\"
  2154. else
  2155. echo shar: Extracting \"diff.mem\" \(9327 characters\)
  2156. sed "s/^X//" >diff.mem <<'END_OF_diff.mem'
  2157. X
  2158. X
  2159. XJan 13 13:00 1988  CDIFF.MEM Page 1
  2160. X
  2161. X
  2162. X
  2163. X     Diff maintains all information needed to compare the two files in
  2164. X     main memory. This means that very large files (or fairly large
  2165. X     files with many differences) will cause the program to abort with
  2166. X     an "out of space" error. Main memory requirements (in words) are
  2167. X     approximately:
  2168. X
  2169. X      2 * (length of file1 + length of file2) + (3 * number of changes)
  2170. X
  2171. X     The diff algorithm reads each file twice (once to build hash
  2172. X     tables and a second time to check for fortuitous matches), then
  2173. X     reads the differences by seeking randomly within the files. CPU
  2174. X     time requirements include sorting the two hash vectors and
  2175. X     randomly searching memory tables for equivalence classes. For
  2176. X     example, running in Vax compatibility mode, two 1000 line files
  2177. X     with a fair number of differences took about 25 seconds (elapsed
  2178. X     wall clock time) for processing. Most of this time was spent in
  2179. X     the file read routines. This test required slightly more than
  2180. X     6000 words of memory for internal tables.
  2181. X
  2182. X     The diff algorithm was developed by J. W. Hunt and M. D. McIlroy,
  2183. X     using a central algorithm defined by H. S. Stone. The algorithm
  2184. X     was described in:
  2185. X
  2186. X          Hunt, J. W., and McIlroy, M. D.,
  2187. X          An Algorithm for Differential File Comparison,
  2188. X          Computing Science Technical Report #41,
  2189. X          Bell Laboratories, Murray Hill, NJ  07974
  2190. X
  2191. X     The following description is summarized from that document. While
  2192. X     it has been slightly modified to correspond to the program
  2193. X     source, the algorithm is essentially identical.
  2194. X
  2195. X     1. Read the input files, building two vectors containing the line
  2196. X     number (serial) and hash value (hash) of each line. Data for
  2197. X     fileA will be in a vector pointed to by fileA[], while data for
  2198. X     fileB will be pointed to by fileB[]. The lengths (number of
  2199. X     lines) of the files will be represented by lenA and lenB
  2200. X     respectively. [This is slightly different from the published
  2201. X     algorithm.]
  2202. X
  2203. X     2. Note initial and final sequences that have identical hash
  2204. X     values to shorten subsequent processing. Note that the "jackpot"
  2205. X     phase (step 9.) will examine all lines in the file. Next, sort
  2206. X     each file using hash as the primary key and serial as the
  2207. X     secondary key.
  2208. X
  2209. X     3. Construct an array of equivalence classes (member[1..lenB])
  2210. X     where each element contains the line number in fileB and a flag
  2211. X     which is True if the indicated line is the first member of an
  2212. X     equivalence class. (An equivalence class is a set of lines which
  2213. X     all hash to the same value. The lines themselves are not
  2214. X     necessarily identical.)
  2215. X
  2216. X     4. Construct an array, class[1..lenA], where each element, I, is
  2217. X     set to the index of a line, J, in fileB if member[J] is the first
  2218. X
  2219. X
  2220. X
  2221. X
  2222. X
  2223. X
  2224. X
  2225. XJan 13 13:00 1988  CDIFF.MEM Page 2
  2226. X
  2227. X
  2228. X     element in an equivalence class and the hash code of line[I] in
  2229. X     fileA is the same as the hash code of line[J] in fileB. Class[I]
  2230. X     is set to zero if no such line exists.
  2231. X
  2232. X     If non-zero, class[I] now points in member[] to the beginning of
  2233. X     the class of lines in fileB equivalent to line[I] in fileA.
  2234. X
  2235. X     The next two steps implement the longest common subsequence
  2236. X     algorithm.
  2237. X
  2238. X     5. Structure CANDIDATE { a, b, previous }, where a and b are line
  2239. X     numbers and previous a reference to a candidate, will store
  2240. X     candidate lists as they are constructed.
  2241. X
  2242. X     Vector clist[] stores references to candidates. It is dimensioned
  2243. X     (0..min(lenA, lenB) + 1)
  2244. X
  2245. X      Initialize
  2246. X          clist[0] = CANDIDATE {   0,   0, -1 };
  2247. X          clist[1] = CANDIDATE { A+1, B+1, -1 };
  2248. X          ktop = 1;
  2249. X
  2250. X     clist[1] is a fence beyond the last usefully filled element and
  2251. X     -1 is an out-of-range clist index. Ktop is the index of the
  2252. X     fence. Note, because of the memory allocation used, clist[] is
  2253. X     actually composed of two vectors, clist[] containing the
  2254. X     candidate reference, and klist[] containing pointers to clist.
  2255. X
  2256. X     6.  For (A = 1 to lenA) {
  2257. X          I = class[A];  -- the index in member[]:  beginning of
  2258. X                -- the class of lines in fileB equivalent
  2259. X                -- to this line in fileA.
  2260. X          if (I is non-zero) {
  2261. X            Merge each member into the candidate list
  2262. X            as discussed below.
  2263. X          }
  2264. X
  2265. X     Unravel the chain of candidates, getting a vector of common
  2266. X     subsequences:
  2267. X
  2268. X     7.  Set all elements of match[0..lenA] to zero.
  2269. X
  2270. X     8. clist[ktop-1] points to the subsequence chain head. For each
  2271. X     element in the chain, let A and B be the line number entries.
  2272. X     Then, set
  2273. X
  2274. X          match[A] = B;
  2275. X
  2276. X     The non-zero elements of match[] now pick out a longest common
  2277. X     subsequence chain, possibly including spurious matches due to
  2278. X     hash coincidences. The pairings between the two files are:
  2279. X
  2280. X      if (match[A] is non-zero) {
  2281. X          line A in fileA matches line match[A] in fileB;
  2282. X      }
  2283. X
  2284. X
  2285. X
  2286. X
  2287. X
  2288. X
  2289. X
  2290. X
  2291. XJan 13 13:00 1988  CDIFF.MEM Page 3
  2292. X
  2293. X
  2294. X     Now, read each line of fileA and fileB to check for jackpots:
  2295. X
  2296. X     9.  for (A = 1 to lenA) {
  2297. X          if (match[A] is nonzero) {
  2298. X            if (fileA[A] is not identical to fileB[match[A]])
  2299. X                match[A] = 0;  -- Hash congruence
  2300. X          }
  2301. X      }
  2302. X
  2303. X     Ignoring "squish" complications, the merge step may be defined as
  2304. X     follows:
  2305. X
  2306. X      Entry:
  2307. X          clist[]      Candidate pointer array
  2308. X          ktop      Fence beyond last filled index
  2309. X          A      Current index in fileA
  2310. X          member[]  Equivalence vector
  2311. X          I      The index in member[] of the first element
  2312. X                  of the class of lines in fileB that are
  2313. X                  equivalent to line[A] in fileA.
  2314. X
  2315. X     1. Let clist[R] be "an r-candidate" and C a reference to the last
  2316. X     candidate found, which will always be an r-candidate. clist[R]
  2317. X     will be updated with this reference once the previous value of
  2318. X     clist[R] is no longer needed. Initialize:
  2319. X
  2320. X         R = 0; C = clist[0];
  2321. X
  2322. X     2.  Do steps 3 through 6 repeatedly:
  2323. X
  2324. X     3. set B to the line number in member[I]; search clist[R..ktop]
  2325. X     for an element, clist[S], such that
  2326. X
  2327. X          clist[S-1].b < B and clist[S].b >= B
  2328. X
  2329. X     Note that clist[] is ordered on clist[].b so that binary search
  2330. X     will work. The search algorithm used requires the two "fence"
  2331. X     entries described above.
  2332. X
  2333. X     If such an element is found, perform steps 4. and 5.
  2334. X
  2335. X     4. Extend the longest common subsequence chain:
  2336. X
  2337. X          If (clist[S].b > B) {
  2338. X            clist[R] = C;
  2339. X            R = S;
  2340. X            C = candidate(A, B, clist[S - 1]);
  2341. X          }
  2342. X
  2343. X     5. Extend the number of subsequences, moving the fence:
  2344. X
  2345. X          If (S == ktop) {
  2346. X            clist[ktop + 1] = clist[ktop]
  2347. X            ktop = ktop + 1;
  2348. X            break out of step 2's loop;
  2349. X          }
  2350. X
  2351. X
  2352. X
  2353. X
  2354. X
  2355. X
  2356. X
  2357. XJan 13 13:00 1988  CDIFF.MEM Page 4
  2358. X
  2359. X
  2360. X
  2361. X      6.  I = I + 1;
  2362. X          if (member[I] is the first element in another class) {
  2363. X              break out of step 2's loop;
  2364. X           }
  2365. X          else {
  2366. X              continue at step 2.
  2367. X           }
  2368. X
  2369. X     7. clist[R] = C; exit merge subroutine.
  2370. X
  2371. X     To illustrate vector contents, here is a sample run:
  2372. X
  2373. X     File A:
  2374. X      line 1
  2375. X      line 2
  2376. X      line 3
  2377. X      line 4
  2378. X      line 5 gets deleted
  2379. X      line 6
  2380. X
  2381. X     File B:
  2382. X      line 1
  2383. X      line 1.5 inserted
  2384. X      line 2
  2385. X      line 3 changed
  2386. X      line 4
  2387. X      line 6
  2388. X
  2389. X     (For clarity, the "squish" step is omitted from the following)
  2390. X
  2391. X     On entry to equiv() (after readin and sorting), the file[] vector
  2392. X     is as follows (the first entry in each pair is the line number,
  2393. X     the second is the hash value. Entries are sorted on hash value):
  2394. X
  2395. X     FileA[] (1..lines in fileA):
  2396. X       line   hash
  2397. X      3 042400  6 043300  5 050026  1 102201  2 102701  4 103501
  2398. X     FileB[] (1..lines in fileB):
  2399. X      6 043300  2 045600  1 102201  3 102701  5 103501  4 147166
  2400. X
  2401. X
  2402. X     After Equiv has processed file[]:
  2403. X
  2404. X     FileA[] (1..lines in fileA):
  2405. X       line value
  2406. X      3 0  6 1  5 0  1 3  2 4  4 5
  2407. X     Member[] (0..lines in fileB)
  2408. X      0  -6  -2  -1  -3  -5  -4
  2409. X
  2410. X     After unsort() has unwound fileB:
  2411. X
  2412. X     Class[] (1 .. lines in fileA):
  2413. X      3   4  0  5  0  1
  2414. X
  2415. X     Within unravel(), match is built in the following order:
  2416. X
  2417. X
  2418. X
  2419. X
  2420. X
  2421. X
  2422. X
  2423. XJan 13 13:00 1988  CDIFF.MEM Page 5
  2424. X
  2425. X
  2426. X
  2427. X      match[6] := 6
  2428. X      match[4] := 5
  2429. X      match[2] := 3
  2430. X      match[1] := 1
  2431. X
  2432. X     Match[] (0 .. lines in fileA):
  2433. X
  2434. X       0  1  3  0  5  0  6
  2435. X
  2436. X     Output is as follows:
  2437. X
  2438. X      1a2
  2439. X      > line 1.5 inserted
  2440. X      3c4
  2441. X      < line 3
  2442. X      ---
  2443. X      > line 3 changed
  2444. X      5d5
  2445. X      < line 5 gets deleted
  2446. X
  2447. X********************************************************************
  2448. X
  2449. X/*
  2450. X *        s t r e q . c
  2451. X */
  2452. X
  2453. X
  2454. XString Equality Test
  2455. XString equality test
  2456. X
  2457. XSynopsis:
  2458. X  streq(a, b);
  2459. X  char      *a;
  2460. X  char      *b;
  2461. X
  2462. XDescription:
  2463. X
  2464. X  Return TRUE if the strings are equal.
  2465. X
  2466. XBugs
  2467. X
  2468. X***************************************************************
  2469. X
  2470. X/*
  2471. X *        e r r o r . c
  2472. X */
  2473. X
  2474. X
  2475. XFatal Error Exit
  2476. X
  2477. X    Synopsis:
  2478. X
  2479. X      _error()
  2480. X
  2481. X      error(format, args)
  2482. X
  2483. X
  2484. X
  2485. X
  2486. X
  2487. X
  2488. X
  2489. XJan 13 13:00 1988  CDIFF.MEM Page 6
  2490. X
  2491. X
  2492. X      char      *format;
  2493. X
  2494. X    Documentation:
  2495. X
  2496. X      Fatal error exits.  _error() halts, error() prints something
  2497. X      on stderr and then halts.
  2498. X
  2499. X    Bugs:
  2500. X
  2501. X      THIS DOES NOT WORK ON MANY SYSTEMS DUE TO EXTREMLY NON-PORTABLE CODE.
  2502. X      Why oh why can't people learn to use varargs properly?  This code will
  2503. X      blow up on OSK.  Fortunatly, it isn't used often...
  2504. X
  2505. X
  2506. X
  2507. X
  2508. X
  2509. X
  2510. X
  2511. X
  2512. X
  2513. X
  2514. X
  2515. X
  2516. X
  2517. X
  2518. X
  2519. X
  2520. X
  2521. X
  2522. X
  2523. X
  2524. X
  2525. X
  2526. X
  2527. X
  2528. X
  2529. X
  2530. X
  2531. X
  2532. X
  2533. X
  2534. X
  2535. X
  2536. X
  2537. X
  2538. X
  2539. X
  2540. X
  2541. X
  2542. X
  2543. X
  2544. X
  2545. X
  2546. X
  2547. X
  2548. X
  2549. X
  2550. X
  2551. X
  2552. X
  2553. END_OF_diff.mem
  2554. if test 9327 -ne `wc -c <diff.mem`; then
  2555.     echo shar: \"diff.mem\" unpacked with wrong size!
  2556. fi
  2557. # end of overwriting check
  2558. fi
  2559. echo shar: End of shell archive.
  2560. exit 0
  2561.